The pattern of access requests by a host processor to a specific logical volume of a storage device in a cached disk storage system may contain a mixture of random and sequential patterns during any given time frame. This mixture may be caused by changes in the access request patterns presented by the host applications, and by the presence of multiple data sets on a given logical volume of a storage device. Storage management software programs, such as the System Managed Storage program, can complicate the mixture even more by changing the placement of multiple data sets on any given volume over time. Disk storage locations for a mainframe host can be logically described by its logical device, cylinder, track and record address. Other systems may use Logical Block Addresses (LBA). Sequential patterns or streams occur when the host application accesses these locations in increasing address sequences such as increasing cylinder, track or record number or increasing LBA. Any reference to sequential detection using cylinder, track or record number, and references to prestaging tracks into cache can be easily extended by one skilled in the art to apply to sequential detection for LBA addressing and prestaging appropriate LBAs into cache.
Modern storage subsystems frequently employ one or more levels of mapping of logical disk addresses as presented and referenced by the host to physical storage locations in the storage subsystem such as cache memory locations and/or physical disk locations. For example it is very common to map Count, Key and Data (CKD) addressing for a large number of logical devices from mainframe hosts to LBA addressing on a much smaller number of physical disk drives. The invention described here is largely independent of the mapping schemes employed. Unless otherwise stated, the sequential detection schemes described are in reference to the host view of data addresses. The mapping or translation of these addresses into physical addresses on the actual hard disk drives that store data, even for the purpose of prestaging the desired data into cache memory, is carried out by methods outside the scope of this invention.
Performance of cached disk storage systems is improved by prestaging tracks or logical blocks from the storage devices into cache memory when sequential access request patterns occur. Host sequential patterns are sometimes also referred to as sequential streams. Host programs which access tracks or logical blocks in sequential order may set special flags in the sequence of commands presented to the storage subsystem to provide explicit sequential access hints. The storage subsystem may also recognize particular command sequences which result from executing programs which access data in sequential order. These command sequences provide implicit hints of sequential access, referred to later as prestaging hints. Alternatively the subsystem may detect the sequential nature of a group of access requests. Sequential patterns may occur concurrently with other sequential requests or with otherwise independent or random access requests on a given logical volume. When a sequential pattern is detected, either due to hints or due to software detection of the sequential nature of access patterns, one or more tracks or LBAs are prestaged into the cache memory in anticipation of a subsequent access request. The intent is to change what would otherwise be a cache miss into a cache hit which reduces the service time as seen by the host processor. In order to increase the probability of having a track in cache by the time the host accesses that track, prestaging processes should prestage some number of tracks ahead of the current access and then maintain prestaging a sufficient number of tracks ahead of the host access to allow time for the tracks to be staged from disk. The number of tracks ahead of the current access will be referred to as the prestage factor. The prestage factor may vary for different scenarios such as different sequential hints, different command types or recent history of sequential patterns that indicate that sequential access is likely to continue. Effective prestaging methods must coordinate the use of sequential hints presented directly by the host processors, implied hints contained in the channel programs, and sequential detection methods where no hints are present. Effective prestaging methods must also record which tracks have already been prestaged to avoid requesting the prestaging of the same tracks multiple times which would waste valuable storage subsystem processing cycles and possibly even back-end bandwidth. It is desirable to only prestage those additional tracks necessary to maintain a desired prestage factor ahead of the current host access.
Simple sequential detection methods compare the address of the requested track with the just previously accessed track for a given volume or device. This approach works well for single streams of access requests, but fails to maintain sequential detection and prestaging when multiple sequential streams are executed concurrently for the same logical device, or when one or more sequential streams execute concurrently with random access requests on that logical device. Multiple concurrent streams of access frequently occur as a result of multiple applications accessing the same logical volume. One approach to solving this problem is to record information in the logical track directory entries of each logical storage device. This information would indicate which tracks are part of a sequential pattern and which tracks have been prestaged. However, in a disk storage system with a large number of possible directory entries, it is expensive to keep a directory entry for every possible track in a fast access type memory to allow the rapid checking of prior track directory entries for sequential detection, making this approach impractical.